package com.hyt.it.ogt.kq.common.utils;

import com.hyt.loginfo.model.Tree;
import org.apache.commons.collections.CollectionUtils;

import java.util.*;

public class TreeToListConverter {
    public static List<List<Tree>> convertTreeToList(List<Tree> root) {
        List<List<Tree>> result = new ArrayList<>();
        Map<String, Tree> map = new HashMap<>();
        convertTreeToListDFSHelper(root, result, map);
        return result;
    }

    private static void convertTreeToListDFSHelper(List<Tree> node, List<List<Tree>> result, Map<String, Tree> map) {
        if (node == null) {
            return;
        }
        // 然后递归处理子节点的子树
        for (Tree child : node) {
            map.put(child.getId(), child);
            if (CollectionUtils.isEmpty(child.getChildren())) {
                List<Tree> data = build(child, map);
                Collections.reverse(data);
                result.add(data);
            } else {
                convertTreeToListDFSHelper(child.getChildren(), result, map);
            }
        }
    }

    private static List<Tree> build(Tree child, Map<String, Tree> map) {
        List<Tree> list = new ArrayList<>();
        list.add(child);
        Tree tree = map.get(child.getPid());
        if(Objects.nonNull(tree)) {
            list.addAll(build(tree, map));
        }
        return list;
    }
}
